/*
Binary Tree Preorder Traversal Total Accepted: 73105 Total Submissions: 201680 My Submissions Question Solution
Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Given {1,2,3,4}, reorder it to {1,4,2,3}.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}



class Solution1 {
public:
	void corePreTraversal(TreeNode* root, vector<int> &res)
	{
		if (root==NULL)
		{
			return;
		}
		res.push_back(root->val);
		corePreTraversal(root->left,res);
		corePreTraversal(root->right,res);
	
	}
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> result;
		if (root == NULL)
		{
			return result;
		}

		corePreTraversal(root,result);
		return result;

	}
};



class Solution2 {
public:
	
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> result;
		if (root == NULL)
		{
			return result;
		}
		stack<TreeNode*> stackTree;
		
		while (root!=NULL||!stackTree.empty())
		{
			if (root!=NULL)
			{
				while (root)
				{
					result.push_back(root->val);
					stackTree.push(root);
					root = root->left;

				}
			}
			else
			{
				root = stackTree.top()->right;
				stackTree.pop();
			}
		}
		
		return result;
	}
};



class Solution {
public:

	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> result;
		if (root == NULL)
		{
			return result;
		}
		stack<TreeNode*> stackTree;
		TreeNode* p = root;

		if (p!=NULL)
		{
			stackTree.push(root);
		}
		
		while (!stackTree.empty())
		{
			p = stackTree.top();
			stackTree.pop();
			result.push_back(p->val);
			if (p->right!=NULL)
			{
				stackTree.push(p->right);

			}
			if (p->left != NULL)
			{
				stackTree.push(p->left);

			}

		}

		return result;
	}
};
int main(int argc, char* argv[])
{

	TreeNode *root = new TreeNode(1);
	TreeNode *root1 = new TreeNode(2);
	TreeNode *root2 = new TreeNode(3);

	root->right = root1;
	root1->left = root2;

	
	vector<int> result;


	Solution s;
	result = s.preorderTraversal(root);

	
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;